package main

import "fmt"

func fibLoop(n int) int {
	switch {
	case n < 0:
		panic("n is negative")
	case n == 0:
		return 1
	case n == 1 || n == 2:
		return 1
	}
	a, b := 1, 1
	for i := 0; i < n-2; i++ {
		a, b = b, a+b
	}
	return b
}

// 1、递推公式，请提供一个 map 用来缓存计算过的 n 对应的结果 提高效率
func fib1(n int) int {
	// 一定要有边界条件
	if n == 1 || n == 2 {
		return 1
	} else if n < 0 {
		panic("n is negative")
	} else if n == 0 {
		return 0
	}
	return fib1(n-1) + fib1(n-2)
}

// 2 如果算法使用循环完成，循环改函数调用，一趟趟循环改为1 次次函数调用
func fib2(n, a, b int) int {
	// 一定要有边界条件
	switch {
	case n < 0:
		panic("n is negative")
	case n == 0:
		return 1
	case n == 1 || n == 2:
		return b
	}
	a, b = b, a+b
	fib2(n-1, a, b)
	return fib2(n-1, a, b)
}

// map 版本
var memo = make(map[int]int)

func fib3(n int) int {
	// 边界条件
	if n == 0 {
		return 0
	}
	if n == 1 || n == 2 {
		return 1
	}
	if n < 0 {
		panic("n cannot be negative")
	}

	// 检查缓存
	if val, ok := memo[n]; ok {
		return val
	}

	// 递归计算并缓存结果
	result := fib1(n-1) + fib1(n-2)
	memo[n] = result
	return result
}

func main() {
	// for i := 0; i < 15; i++ {
	// 	fmt.Println(i, fibLoop(i), fib1(i), fib2(i, 1, 1))
	// }
	fmt.Println(1, fibLoop(45))
	fmt.Println(2, fib2(45, 1, 1))
	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~")
	fmt.Println(3, fib1(45))
	fmt.Println(4, fib3(45))
}
